漫画：知乎面试题（旋转数组最小值Ⅱ - 进阶版）

今天是小浩算法“365刷题计划”第72天。继续为大家讲解二分法系列篇 - 旋转排序数组最小值Ⅱ（进阶版）。话不多说，直接看题：

01PART旋转排序数组最小值Ⅱ

昨天为大家讲解了元素不可重复的版本，那如果元素重复该如何处理呢？

第154题：假设按照升序排序的数组在预先未知的某个点上进行了旋转。( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。请找出其中最小的元素。

注意数组中可能存在重复的元素。

示例 1：

输入: [1,3,5]

输出: 1

示例 2：

输入: [2,2,2,0,1]

输出: 0

说明：

这道题是 寻找旋转排序数组中的最小值 的延伸题目。

允许重复会影响算法的时间复杂度吗？会如何影响，为什么？

02PART题目回顾

之前我也说过，通过改变题中条件，使得题目难度上升的做法。在算法题目的设计中，是一种非常常见的手段。本题就是这样，从中等变成了困难。

（通过改变题目，使得难度上升）

在讲解本题之前，首先要对昨天的题目进行一个答疑。昨天有人问我为什么题目中讲的是与left进行比较，但是最后代码中写的时候变成了和right比较。这个确实是我讲的时候讲忘了，但是这其实是一个思维转化的问题：因为在旋转之前的原数组是一个递增序列，那一定是左边的数小，右边的数大，而我们要找的是最小值，所以比较偏向左找。那如果和left进行比较，其实也是完全ok的，那我们的思路就变成了找到偏右的最大值，进而向右再移动一位，自然也就是最小值。如果不能理解的话，可以回顾一下昨天的文章：

并且我这里对昨天的题目，补上一个和left对比的版本，供大家参考学习（昨天没有给Go的示例，所以今天补一个Go的）

 1//go
 2func findMin(nums []int) int {
 3    left, right := 0, len(nums)-1
 4    for left < right {
 5        mid := left + (right-left)>>1 + 1
 6        if nums[left] < nums[mid] {
 7            left = mid
 8        } else if nums[left] > nums[mid] {
 9            right = mid - 1
10        }
11    }
12    return nums[(right+1)%len(nums)]
13}

上面的代码有两处需要说明，第一：mid中最后加1的目的，是为了使得mid更加靠近right，增加容错性。当然，你写到里边也是可以的，甚至更好。我怕大家看不懂，所以写在外面了。第二：最后一行代码取模，是需要考虑最大值刚好在最右边的情况。

03PART题解分析

二分查找的本质，其实就是通过收敛查找空间，找到目标值的一种方式。请大家认真阅读这句话。不管是采用不同的mid定义方式，又或者是不一样的while条件，统统都是为了这个目的。在完成这个目的的基础上，我们才去考虑如何减少冗余代码，减少循环次数等等，完成进一步的优化。

现在再来看今天的题目。相对比昨天题目而言，其实只是多了nums[mid] 等于 nums[right] 时的额外处理。（当然， 如果是和left进行比较，就是nums[mid]等于nums[left]）

对比一下下面两个图：

（无重复）

（有重复）

其实直接就可以给出代码了：

 1//java
 2class Solution {
 3    public int findMin(int[] nums) {
 4        int left = 0;
 5        int right = nums.length - 1; 
 6        while (left < right) {
 7            int mid = left + (right - left) / 2;
 8            if (nums[mid] > nums[right]) {
 9                left = mid + 1;
10            } else if (nums[mid] < nums[right]) {
11                right = mid;
12            } else {
13                right--;
14            }
15        }
16        return nums[left];
17    }
18};

郑重申明（读我的文章必看）：

• 本系列所有教程都不会用到复杂的语言特性，大家无须担心没有学过相关语法，算法思想才是最重要的！

• 作为学术文章，虽然风格可以风趣，但严谨，我是认真的。本文所有代码均在leetcode进行过测试运行。

如果我们再对比一下代码的差异，就会非常的明显：

（左边是有重复，右边是无重复）

可以看到在 nums[mid] 等于 nums[right] 时的情况下，我们只多了一个 right-1 的操作。这里需要额外说明的是，为什么要这样做？我看leetcode上的题解，这块很多都是长篇大论，其实没那么复杂，一句话就可以给你讲明白，看看下面这个！

因为 mid 和 right 相等时，最小值既可能在左边，又可能在右边，所以此时自然二分思想作废，咱们就砍掉一个右边界。说白了，就是让子弹再飞一会儿。

如果想看其他二分法系列的，可以看以下内容：

如果你问我对学习算法有什么建议，这篇文章是必看的：

 小浩算法，每日一题

关注领取《图解算法》高清版

进群的小伙伴请加右侧私人微信（备注：进群）